package com.leetcode.根据数据结构分类.数组;

/**
 * @author: xiaomi
 * @date: 2021/1/24
 * @description: 35. 搜索插入位置
 * https://leetcode-cn.com/problems/search-insert-position/
 */
public class A_35_搜索插入位置 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 5, 6};
        nums = new int[]{1, 3};
        int target = 7;
        target = 2;
        A_35_搜索插入位置 action = new A_35_搜索插入位置();
        int res = action.searchInsert(nums, target);
    }

    /**
     * 将 计划元素 查找/插入 到数组中
     *
     * @param nums   原数组
     * @param target 计划元素
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int begin = 0, mid = 0;
        int end = nums.length;
        while (begin < end) {
            mid = (begin + end) >> 1;
            int compare = nums[mid] == target ? 0 : (nums[mid] < target ? -1 : 1);
            if (compare == 0) {
                return mid;
            } else if (compare == -1) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        //需要对最后的边界进行判断
//        if (begin < nums.length) {
//            if (nums[begin] < target) {
//                return begin + 1;
//            }
//        }
//        return begin;
        //如果符合 [) 的规则，就不需要再额外判断了
        return begin;
    }
}
